#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#       miia2.py
#       
#       Copyright 2010 santiago <santiagopaleka@gmail.com>
#       
#       This program is free software; you can redistribute it and/or modify
#       it under the terms of the GNU General Public License as published by
#       the Free Software Foundation; either version 2 of the License, or
#       (at your option) any later version.
#       
#       This program is distributed in the hope that it will be useful,
#       but WITHOUT ANY WARRANTY; without even the implied warranty of
#       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#       GNU General Public License for more details.
#       
#       You should have received a copy of the GNU General Public License
#       along with this program; if not, write to the Free Software
#       Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
#       MA 02110-1301, USA.

import random as r
import time as t
tablaDistancias = ((2,1,2,1,0,1,2,1,2),(0,1,2,1,2,3,2,3,4),(1,0,1,2,1,2,3,2,3),
    (2,1,0,3,2,1,4,3,2),(3,2,1,2,1,0,3,2,1),(4,3,2,3,2,1,2,1,0),
    (3,2,3,2,1,2,1,0,1),(2,3,4,1,2,3,0,1,2),(1,2,3,0,1,2,1,2,3))
libertades = ((1,3),(0,4,2),(1,5),(0,4,6),(1,3,5,7),(2,4,8),(3,7),(6,4,8),(5,7))
fin = (1,2,3,8,0,4,7,6,5)

def main():
    miTablero = tablero()
    miTablero.imprimir()  
    print ""
    miTablero.desordenar()
    miTablero.pospadre = miTablero.posiciones
    miTablero.imprimir()  
    print "el tablero tiene " + str(miTablero.cuantosMal())+ " posiciones mal"
    print ""
    while miTablero.ordenar():
        pass 
    return
    
class tablero:
    def __init__(self,posiciones = [1,2,3,8,0,4,7,6,5], posiciones_padre = [1,2,3,8,0,4,7,6,5]):
        self.posiciones = posiciones
        self.pospadre = posiciones_padre
        return None
        
    def imprimir(self):
        for j in range(0,7,3):
            for i in range(3): print(str(self.posiciones[i+j])+" |"),
            print "\n-----------"
    
    def desordenar(self):
        """desordena los items del atributo tablero"""
        r.shuffle(self.posiciones)
    
    def costo(self):
        return self.cuantosMal()+self.distancias()
    
    def cuantosMal(self):
        """cuenta cuantos elementos de la lista están en su lugar deseado"""
        mal = 0
        for i in range(9):
            if self.posiciones[i] != fin[i]:
                mal+=1
        return mal
        
    def distancias(self):
        dist = 0
        for i in range(9):
            donde = self.posiciones.index(i)
            dist +=  tablaDistancias[i][donde]
        return dist
    def ordenar(self):
        self.h = self.distancias() + self.cuantosMal()
        if self.h == 0:
            return 0
        tableros=[]
        donde = self.posiciones.index(0)
        print "el cero está en: " + str(donde) +"\n"
        for i in libertades[donde]:
            hijo = self.posiciones[:]
            aux = hijo[i]
            hijo[i] = hijo[donde]
            hijo[donde]= aux
            if hijo != self.pospadre:
                tableros.append(tablero(hijo))
                tableros[-1].imprimir()
                print tableros[-1].costo()
        num = 50
        for i in tableros:
            if (i.costo() < num):
                num = i.costo()
                mejortablero = i
        mejortablero.imprimir()
        self.pospadre = self.posiciones
        self.posiciones = mejortablero.posiciones
        return 1
        
if __name__ == '__main__': main()
